package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _16接雨水
 * @description
 * @date 2023/07/13 9:51
 * <p>
 * ******************************************************
 */
public class _16接雨水 {

    public int trap(int[] height) {
        int n = height.length;

        int[] left_max = new int[n];
        left_max[0] = height[0];
        int[] right_max = new int[n];
        right_max[n - 1] = height[n - 1];

        for (int i = 1; i < n; i++) {
            left_max[i] = Math.max(height[i], left_max[i - 1]);
        }


        for (int i = n - 2; i >= 0; i--) {
            right_max[i] = Math.max(height[i], right_max[i + 1]);
        }

        int sum = 0;

        for (int i = 0; i < n; i++) {
            sum += (Math.min(left_max[i], right_max[i]) - height[i]);
        }

        return sum;
    }
}
